package Text21;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    //    第一行包含两个整数 N和 K。
//    以下 N行每行一个整数 Ai。
    static int N = 100010;
    static int mod = 1000000009;
    static int[] a = new int[N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        Arrays.sort(a, 0, n);
        int l = 0, r = n - 1, sign = 1;
        int res = 1;
        if (k % 2 == 1) {
            res = a[r--];
            k--;
            if (res < 0) {
                sign = -1;
            }
        }
        while (k > 0) {
            long x = (long) a[l] * a[l + 1];
            long y = (long) a[r] * a[r - 1];
            if (sign * x > sign * y) {
                res = (int) (x % mod * res % mod);
                l += 2;
            } else {
                res = (int) (y % mod * res % mod);
                r -= 2;
            }
            k -= 2;
        }
        System.out.println(res);
    }
}
